#include <cstdio>

int GetFactorialNumberCount(int n, int a){
    int ans[2600] = {};
    int len=1;
    ans[0] = 1;
    for(int i=2;i<=n; i++){
        for (int j=0;j<len;j++){
            ans[j] *= i;
        }

        for (int j=0;j<len;j++){
            ans[j+1] += ans[j]/10;
            ans[j] %= 10;
        }

        while(ans[len]){
            ans[len+1] += ans[len]/10;
            ans[len++] %= 10;
        }
    }

    int cnt=0;
    for(int i=len-1;i>=0;i--){
        if(ans[i]==a){
            cnt++;
        }
    }

    return cnt;
}
/**
 * https://www.luogu.com.cn/problem/P1591
 * 
 * 阶乘高精度
 * 
 */
int main(){

    int t;
    scanf("%d", &t);

    while(t--){
        int n, a;
        scanf("%d %d", &n, &a);
        printf("%d\n", GetFactorialNumberCount(n, a));
    }

    return 0;
}

